Chris Pollett >
Old Classses > |
HW#5 --- last modified February 06 2019 04:20:47..Due date: May 11
Files to be submitted: Purpose: To gain experience with NP-completeness proofs and approximation algorithms. Related Course Outcomes: The main course outcomes covered by this assignment are: LO6 -- Given a problem determine within NP that is promised to be either in P or NP-complete prove which LO7 -- Analyze or code an approximation algorithm for a optimization problem whose decision problem is NP-complete. Specification: This homeworks consists of the following written problems, together with a programming exercise described below. Submit the written problems in Hw5.pdf as part of your Hw5.zip file. Submit your code in this ZIP file as well.
For the coding part of the assignment I would like you to code the approximate vertex cover algorithm discussed in class and submit this in a file ApproxVertexCover.java as part of your HW5.zip file. This program will be compiled from the command line with the syntax: javac ApproxVertexCover.java It will then be run with a line like: java ApproxVertexCover some_file_with_graph.txt Here some_file_with_graph.txt will be a file containing the adjacency matrix for a graph. For example, 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 which corresponds to the graph of Figure 35.1 in the book. On such an input, your program should run the approximate vertex cover algorithm we has and output the vertices in the cover it finds. The edge it should pick in the line pick an arbitrary edge should be chosen uniformly at random from the edgeset `E'`. It should print out the edges chosen. One possible output of the algorithm on the above graph is:
Edges Chosen: (1,2) (4,5) (3,6) Cover Found: 1 2 3 4 5 6 I would like you to test your program on a variety of graph for which you hand calculate the optimal vertex cover and see how this algorithm does versus the optimal. Write up your results in experiments.txt. Point Breakdown
|